package Leetcode.树;

import java.util.*;

/**
 * @Author: kirito
 * @Date: 2024/4/24 11:36
 * @Description:
 * 感染二叉树需要的总时间
 * 中等
 * 相关标签
 * 相关企业
 * 提示
 * 给你一棵二叉树的根节点 root ，二叉树中节点的值 互不相同 。另给你一个整数 start 。在第 0 分钟，感染 将会从值为 start 的节点开始爆发。
 *
 * 每分钟，如果节点满足以下全部条件，就会被感染：
 *
 * 节点此前还没有感染。
 * 节点与一个已感染节点相邻。
 * 返回感染整棵树需要的分钟数。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：root = [1,5,3,null,4,10,6,9,2], start = 3
 * 输出：4
 * 解释：节点按以下过程被感染：
 * - 第 0 分钟：节点 3
 * - 第 1 分钟：节点 1、10、6
 * - 第 2 分钟：节点5
 * - 第 3 分钟：节点 4
 * - 第 4 分钟：节点 9 和 2
 * 感染整棵树需要 4 分钟，所以返回 4 。
 * 示例 2：
 *
 *
 * 输入：root = [1], start = 1
 * 输出：0
 * 解释：第 0 分钟，树中唯一一个节点处于感染状态，返回 0 。
 *
 *
 * 提示：
 *
 * 树中节点的数目在范围 [1, 105] 内
 * 1 <= Node.val <= 105
 * 每个节点的值 互不相同
 * 树中必定存在值为 start 的节点
 */

public class amountOfTime {
/*    *//**
     * 节点值互不相同
     * 感觉有点像层序遍历  记录当前节点的层次+总树的层次，那么就是所需要的时间总数
     * @param root
     * @param start
     * @return
     */
/*    public int amountOfTime(TreeNode root, int start) {
        if (root.left == null && root.right == null) {
            return 0;
        }
        TreeNode node = root;
        //deep[0]  子树深  1 start深度
        int[] leftDeep = new int[2];
        int[] rightDeep = new int[2];
        //-1根  0左 1 右
        dfs(root, start, leftDeep);
        dfs(root, start, rightDeep);
        int lLen = leftDeep[0], lFound = leftDeep[1];
        int rLen = rightDeep[0], rFound = rightDeep[1];
        if (root.val == start) {
            return
        }
        return
    }*/

    private int dfs(TreeNode root, int start, int[] deep) {
        if (root == null) {
            return 0;
        }

        int leftDeep = dfs(root.left, start, deep);
        int rightDeep = dfs(root.right, start, deep);
        int maxDeep = Math.max(leftDeep, rightDeep) + 1;
        deep[0] = maxDeep;
        if (root.val == start) {
            deep[1] = deep[0];
        }
        return maxDeep;
    }
/*
    // 定义一个函数，计算从树的某个节点到任意节点的最短时间（路径长度）
    public int amountOfTime2(TreeNode root, int start) {
        // 创建一个图，用来存储节点之间的邻接关系
        Map<Integer, List<Integer>> graph = new HashMap<Integer, List<Integer>>();
        // 进行深度优先搜索，构建图
        dfs(graph, root);
        // 创建一个队列，用来进行广度优先搜索
        Queue<int[]> queue = new ArrayDeque<int[]>();
        // 将起始节点和时间0加入队列
        queue.offer(new int[]{start, 0});
        // 创建一个集合，用来记录已经访问过的节点
        Set<Integer> visited = new HashSet<Integer>();
        // 添加起始节点到访问集合
        visited.add(start);
        // 初始化时间为0
        int time = 0;
        // 当队列不为空时，继续执行
        while (!queue.isEmpty()) {
            // 从队列中取出一个节点和对应的时间
            int[] arr = queue.poll();
            int nodeVal = arr[0];
            // 更新当前时间
            time = arr[1];
            // 遍历当前节点的所有子节点
            for (int childVal : graph.get(nodeVal)) {
                // 如果子节点还没有被访问过
                if (visited.add(childVal)) {
                    // 将子节点和时间+1后加入队列
                    queue.offer(new int[]{childVal, time + 1});
                }
            }
        }
        // 返回最终的时间，即从起始节点到所有节点的最短路径时间
        return time;
    }

    // 定义一个辅助函数，用于深度优先搜索构建图
    public void dfs(Map<Integer, List<Integer>> graph, TreeNode node) {
        // 如果节点值在图中不存在，则添加，并初始化一个空列表
        graph.putIfAbsent(node.val, new ArrayList<Integer>());
        // 遍历当前节点的左右子节点
        for (TreeNode child : Arrays.asList(node.left, node.right)) {
            // 如果子节点不为空
            if (child != null) {
                // 将当前节点值添加到子节点的邻接列表中
                graph.get(node.val).add(child.val);
                // 同样，将子节点值添加到当前节点的邻接列表中，形成无向图
                graph.putIfAbsent(child.val, new ArrayList<Integer>());
                graph.get(child.val).add(node.val);
                // 递归地对子节点进行深度优先搜索
                dfs(graph, child);
            }
        }
    }*/


/*    private TreeNode startNode;
    private final Map<TreeNode, TreeNode> fa = new HashMap<>();

    public int amountOfTime3(TreeNode root, int start) {
        dfs(root, null, start);
        return maxDepth(startNode, startNode);
    }

    private void dfs(TreeNode node, TreeNode from, int start) {
        if (node == null) {
            return;
        }
        fa.put(node, from); // 记录每个节点的父节点
        if (node.val == start) {
            startNode = node; // 找到 start
        }
        dfs(node.left, node, start);
        dfs(node.right, node, start);
    }

    private int maxDepth(TreeNode node, TreeNode from) {
        if (node == null) {
            return -1; // 注意这里是 -1，因为 start 的深度为 0
        }
        int res = -1;
        if (node.left != from) {
            res = Math.max(res, maxDepth(node.left, node));
        }
        if (node.right != from) {
            res = Math.max(res, maxDepth(node.right, node));
        }
        //遍历父节点 然后再到底层节点
        if (fa.get(node) != from) {
            res = Math.max(res, maxDepth(fa.get(node), node));
        }
        return res + 1;
    }*/

    private int ans;

    public int amountOfTime4(TreeNode root, int start) {
        dfs(root, start);
        return ans;
    }

    private int[] dfs(TreeNode node, int start) {
        if (node == null) {
            return new int[]{0, 0};
        }
        int[] leftRes = dfs(node.left, start);
        int[] rightRes = dfs(node.right, start);
        int lLen = leftRes[0], lFound = leftRes[1];
        int rLen = rightRes[0], rFound = rightRes[1];
        if (node.val == start) {
            // 计算子树 start 的最大深度
            // 注意这里和方法一的区别，max 后面没有 +1，所以算出的也是最大深度
            ans = Math.max(lLen, rLen);
            return new int[]{1, 1}; // 找到了 start
        }
        if (lFound == 1 || rFound == 1) {
            // 只有在左子树或右子树包含 start 时，才能更新答案
            ans = Math.max(ans, lLen + rLen); // 两条链拼成直径
            // 保证 start 是直径端点
            return new int[]{(lFound == 1 ? lLen : rLen) + 1, 1};
        }
        return new int[]{Math.max(lLen, rLen) + 1, 0};
    }


}
